#include <iostream>
#include <stack>
using namespace std;

// class SortedStack {
// private:
//     stack<int> temp_st,min_st;
//     int min = INT_MAX;
//     int flag = 1; 
// public:
//     SortedStack() {

//     }
    
//     void push(int val) {
//         if(val < min)
//         {
//             min = val;
//             min_st.push(min);
//         }
//         else
//         {
//             min_st.pop();
//             min_st.push(val);
//             min_st.push(min);
//         }
//     }
    
//     void pop() {
//         if(min_st.size() == 0) 
//         {
//             min = INT_MAX;
//             return;
//         }
//         min_st.pop();
//         if(min_st.size() > 0)
//         {
//             min = min_st.top();
//             while(!min_st.empty())
//             {
//                 if(min > min_st.top())
//                 {
//                     min = min_st.top();
//                 }
//                 temp_st.push(min_st.top());
//                 min_st.pop();  
//             }
//             while(!temp_st.empty())
//             {
//                 if(min == temp_st.top() && flag)
//                 {
//                     flag = 0;
//                     temp_st.pop();
//                     continue;
//                 }
//                 min_st.push(temp_st.top());
//                 temp_st.pop();
//             }
//             min_st.push(min);
//             flag = 1;
//         }
//     }
    
//     int peek() {
//         if(min_st.size() == 0) return -1;
//         return min_st.top();
//     }
    
//     bool isEmpty() {
//         return min_st.empty();
//     }
// };

// class SortedStack {
// private:
//     stack<int> s1,s2;

// public:
//     SortedStack() {}
    
//     void push(int val) {
//       while(!s1.empty() && s1.top() < val)
//         {
//             s2.push(s1.top());
//             s1.pop();
//         }
//         s1.push(val);
//         while(!s2.empty())
//         {
//             s1.push(s2.top());
//             s2.pop();
//         }
//     }
    
//     void pop() {
//         if(!s1.empty()) 
//             s1.pop();
//     }
    
//     int peek() {
//         if(!s1.empty()) 
//             return s1.top();
//         return -1;
//     }
    
//     bool isEmpty() {
//         return s1.empty();
//     }
// };

class SortedStack {
private:
    stack<int> s1,s2;

public:
    SortedStack() {}
    
    void push(int val) {
        while(!s2.empty() && s2.top() > val)
        {
            s1.push(s2.top());
            s2.pop();
        }
        
        while(!s1.empty() && s1.top() < val)
        {
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(val);
    }
    
    void pop() {
        while(!s2.empty()) 
        {
            s1.push(s2.top());
            s2.pop();
        }
        if(!s1.empty())
            s1.pop();
    }
    
    int peek() {
        while(!s2.empty()) 
        {
            s1.push(s2.top());
            s2.pop();
        }
        if(!s1.empty())
            return s1.top();
        else return -1;
    }
    
    bool isEmpty() {
        return s1.empty() && s2.empty();
    }
};

int main()
{
    SortedStack st;
    cout << st.peek() << endl;
    cout << st.isEmpty() << endl;
    cout << st.peek() << endl;
    st.push(18);
    cout << st.isEmpty() << endl;
    cout << st.peek() << endl;
    st.push(40);
    st.pop();
    cout << st.isEmpty() << endl;
    cout << st.peek() << endl;
    st.push(12);
    st.push(3);
    st.push(38);
    cout << st.isEmpty() << endl;
    cout << st.isEmpty() << endl;
    cout << st.peek() << endl;
    cout << st.peek() << endl;
    st.pop();
    cout << st.peek() << endl;
    st.pop();
    st.pop();
    st.pop();
    cout << st.peek() << endl;
    st.pop();
    st.push(71);
    cout << st.isEmpty() << endl;
    st.pop();
    st.pop();
    st.push(35);
    cout << st.isEmpty() << endl;
    st.push(36);
    st.push(20);
    cout << st.isEmpty() << endl;
    st.pop();
    cout << st.isEmpty() << endl;
    cout << st.isEmpty() << endl;

    st.push(67);
    cout << st.peek() << endl;
    cout << st.isEmpty() << endl;
    st.push(20);
    st.pop();
    cout << st.peek() << endl;
    st.pop();
    st.push(29);
    st.pop();
    cout << st.isEmpty() << endl;
    cout << st.peek() << endl;
    cout << st.isEmpty() << endl;
    st.push(27);
    st.push(45);
    st.push(24);
    st.push(28);
    st.pop();
    st.push(56);
    st.push(32);

    cout << st.isEmpty() << endl;
    st.pop();
    st.pop();
    cout << st.peek() << endl;

    st.push(13);
    st.push(46);

    cout << st.isEmpty() << endl;
    st.push(5);
    cout << st.isEmpty() << endl;
    cout << st.isEmpty() << endl;
    cout << st.peek() << endl;
    cout << st.isEmpty() << endl;
    st.push(67);
    cout << st.isEmpty() << endl;
    cout << st.isEmpty() << endl;
    st.pop();
    cout << st.isEmpty() << endl;
    st.push(15);
    st.pop();
    st.pop();

    st.push(60);
    cout << st.peek() << endl;
    cout << st.peek() << endl;
    cout << st.isEmpty() << endl;
    cout << st.isEmpty() << endl;
    st.pop();
    st.pop();
    st.push(67);
  
    return 0;
}
